package com.arron.algorithm.leetcodetop100.动态规划.背包问题;

public class 分割等和子集 {

    public boolean canPartition(int[] nums) {

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        int n = nums.length;
        //问题转换，是否存在这样两个子集，将这个数组分割成两个子集，使得两个子集的元素和相等。
        // ===> 即 是否存在 有元素和为 sum/2 的子集合
        //定义dp

        if (sum%2 != 0){
            return false;
        }
        int w = sum/2;
        //定义dp dp[i][j] 表示nums中前 i 个元素是否存在 能够凑成总和j 的集合
        boolean[][] dp = new boolean[n+1][w+1];

        //base case
        for (int i = 0; i <= n; i++)
            dp[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= w ; j++) {
                if (j-nums[i-1] <0){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }

    return dp[n][w];

    }

    public boolean canPartitionDFS(int[] nums) {

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        int n = nums.length;
        //问题转换，是否存在这样两个子集，将这个数组分割成两个子集，使得两个子集的元素和相等。
        // ===> 即 是否存在 有元素和为 sum/2 的子集合

        if (sum%2 != 0){
            return false;
        }
        int w = sum/2;
        Boolean[][] mem = new Boolean[n+1][w+1];

        return canPartitionDFS(nums,w,0,mem);
    }


    public boolean canPartitionDFS(int[] nums,int w,int i,Boolean[][] mem) {


        if (i >= nums.length){
            return false;
        }
        if (w < 0){
            return false;
        }
        if (w==0){
            return true;
        }
        if (mem[i][w] != null){
            return mem[i][w];
        }
        mem[i][w] = canPartitionDFS(nums,w-nums[i],i+1,mem) || canPartitionDFS(nums,w,i+1,mem);
        //选择装入
        return  mem[i][w];
    }



}
